#include <iostream>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	node *next;
}node;

// question 1
node *create()
{
	int x = 0;
	node *head, *p, *tail;

	head = (node *)malloc(sizeof(node));

	while(1)
	{
		printf("Please input the data:");
		scanf("%d", &x);
		if(x == 0)
			break;

		p = (node *)malloc(sizeof(node));
		p->data = x;
		if(head->next == NULL)
		{
			head->next = p;
		}
		else
		{
			tail->next = p;
		}

		tail = p;
	}

	tail->next = NULL;

	return head;
}

// question 2
int length(node *head)
{
	int len = 0;
	node *p;

	p = head->next;
	while(p!=NULL)
	{
		len++;
		p = p->next;
	}

	return len;
}

// question 3
void print(node *head)
{
	node *p;
	int index = 0;

	if(head == NULL || head->next == NULL)
	{
		printf("Link is empty!\n");
		return;
	}

	p = head->next;
	while(p != NULL)
	{
		printf("The %dth node is: %d\n", ++index, p->data);
		p = p->next;
	}
}

// question 4
node *search_node(node *head, int pos)
{
	node *p = head->next;

	if(pos < 0)
	{
		printf("incorrect position to search node!\n");
		return NULL;
	}

	if(pos == 0)
	{
		return head;
	}

	if(p == NULL)
	{
		printf("Link is empty!\n");
		return NULL;
	}

	while(--pos)
	{
		if((p = p->next) == NULL)
		{
			printf("incorrect position to search node!\n");
			break;
		}
	}

	return p;
}

// question 5
node *insert_node(node *head, int pos, int data)
{
	node *item = NULL;
	node *p;

	item = (node *)malloc(sizeof(node));
	item->data = data;

	if(pos == 0)
	{
		item->next = head->next;
		head->next = item;
		return head;
	}

	p = search_node(head, pos);
	if(p != NULL)
	{
		item->next = p->next;
		p->next = item;
	}

	return head;
}

// question 6
node *delete_node(node *head, int pos)
{
	node *item = NULL;
	node *p = head->next;

	if(p == NULL)
	{
		printf("link is empty!\n");
		return NULL;
	}

	p = search_node(head, pos-1);
	if(p!=NULL && p->next!=NULL)
	{
		item = p->next;
		p->next = item->next;
		free(item);
	}

	return head;
}

// question 7
node *reverse(node *head)
{
	node *p, *q, *r;

	if(head == NULL || head->next == NULL)
	{
		return head;
	}

	p = head->next;
	q = p->next;
	p->next = NULL;

	while(q != NULL)
	{
		r = q->next;
		q->next = p;
		p = q;
		q = r;
	}
	head->next = p;

	return head;
}

// question 8
node *search_middle(node *head)
{
	int i = 0;
	int j = 0;
	node *cur = NULL;
	node *mid = NULL;

	cur = mid = head->next;
	while(cur != NULL)
	{
		if(i/2>j)
		{
			j++;
			mid = mid->next;
		}
		i++;
		cur = cur->next;
	}

	return mid;
}

int main()
{
	node *head = create();
	printf("Length:%d\n", length(head));
	head = insert_node(head, 2, 5);
	printf("insert integer 5 after 2th node:\n");
	print(head);
	head = delete_node(head, 2);
	printf("delete the 3th node:\n");
	print(head);
	printf("reverse list\n");
	head = reverse(head);
	print(head);

	return 0;
}
